package LeetCode;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class LC_623_AddOneRowtoTree {

    public static void main(String[] args) {

    }

    public class Solution_1 {
        public TreeNode addOneRow(TreeNode t, int v, int d) {
            if (d == 1) {
                TreeNode n = new TreeNode(v);
                n.left = t;
                return n;
            }
            insert(v, t, 1, d);
            return t;
        }

        void insert(int val, TreeNode node, int depth, int n) {
            if (node == null)
                return;
            if (depth == n - 1) {
                TreeNode t = node.left;
                node.left = new TreeNode(val);
                node.left.left = t;
                t = node.right;
                node.right = new TreeNode(val);
                node.right.right = t;
            } else {
                insert(val, node.left, depth + 1, n);
                insert(val, node.right, depth + 1, n);
            }
        }
    }


    public class Solution_2 {
        class Node {
            Node(TreeNode n, int d) {
                node = n;
                depth = d;
            }

            TreeNode node;
            int depth;
        }

        public TreeNode addOneRow(TreeNode t, int v, int d) {
            if (d == 1) {
                TreeNode n = new TreeNode(v);
                n.left = t;
                return n;
            }
            Stack<Node> stack = new Stack<>();
            stack.push(new Node(t, 1));
            while (!stack.isEmpty()) {
                Node n = stack.pop();
                if (n.node == null)
                    continue;
                if (n.depth == d - 1) {
                    TreeNode temp = n.node.left;
                    n.node.left = new TreeNode(v);
                    n.node.left.left = temp;
                    temp = n.node.right;
                    n.node.right = new TreeNode(v);
                    n.node.right.right = temp;

                } else {
                    stack.push(new Node(n.node.left, n.depth + 1));
                    stack.push(new Node(n.node.right, n.depth + 1));
                }
            }
            return t;
        }
    }

    public class Solution_3 {
        public TreeNode addOneRow(TreeNode t, int v, int d) {
            if (d == 1) {
                TreeNode n = new TreeNode(v);
                n.left = t;
                return n;
            }
            Queue<TreeNode> queue = new LinkedList<>();
            queue.add(t);
            int depth = 1;
            while (depth < d - 1) {
                Queue<TreeNode> temp = new LinkedList<>();
                while (!queue.isEmpty()) {
                    TreeNode node = queue.remove();
                    if (node.left != null) temp.add(node.left);
                    if (node.right != null) temp.add(node.right);
                }
                queue = temp;
                depth++;
            }
            while (!queue.isEmpty()) {
                TreeNode node = queue.remove();
                TreeNode temp = node.left;
                node.left = new TreeNode(v);
                node.left.left = temp;
                temp = node.right;
                node.right = new TreeNode(v);
                node.right.right = temp;
            }
            return t;
        }
    }

}